package com.li.algorithm.leetcode.hot100;

public class Test30 {
    /**
     * 解法1：迭代
     *   时间复杂度：O(n)
     *   空间复杂度：O(1)
     */
    public ListNode swapPairs(ListNode head) {
        ListNode pre = new ListNode(-1);
        pre.next = head;
        ListNode p = head;
        head = pre;
        while (p != null && p.next != null) {
            //遍历所有节点
            //交换后进入下一个节点
            ListNode temp = p.next;
            p.next = p.next.next;
            temp.next = p;
            pre.next = temp;
            pre = temp.next;
            p = p.next;
        }
        return head.next;
    }

    /**
     * 解法2：递归
     *   时间复杂度：O(n)
     *   空间复杂度：O(n)
     */
    public ListNode swapPairs2(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        //每一步都当作一次三个节点的交换（其中第三个节点是由递归产生的）
        ListNode newHead = head.next;
        head.next = swapPairs(head.next.next);
        newHead.next = head;
        return newHead;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        ListNode p = head;
        for (int i = 2; i <= 5; i++) {
            p.next = new ListNode(i);
            p = p.next;
        }
        ListNode result = new Test30().swapPairs(head);
        while (result != null) {
            System.out.println(result.val);
            result = result.next;
        }
    }
}
